package leetcode101_xqzhao

// TODO 三数之和 【-】 三指针 | 脑筋急转弯

import "sort"

func threeSum(nums []int) [][]int {
	n := len(nums)
	sort.Ints(nums)
	res := make([][]int, 0)

	for one := 0; one < n; one++ {
		three := n - 1
		backOne := -1 * nums[one]
		// 需要和上一次枚举的数不相同
		if one > 0 && nums[one] == nums[one-1] {
			continue
		}
		for two := one + 1; two < n; two++ {
			// 需要和上一次枚举的数不相同
			if two > one+1 && nums[two] == nums[two-1] {
				continue
			}
			// 如果 nums[two]+nums[three] > backOne, 则 three--
			for ; three > two && nums[two]+nums[three] > backOne; three-- {

			}
			if two == three {
				break
			}
			if nums[two]+nums[three] == backOne {
				res = append(res, []int{nums[one], nums[two], nums[three]})
			}
		}
	}

	return res
}
